package com.asia.algorithmcode.binaryTree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @DESCRIPTION: 111、二叉樹的最小深度
 * @USER: wanfu
 * @DATE: 2025/5/12 星期一 17:34
 */
public class MinDepth {

    public static void main(String[] args) {
        TreeNode t3 = new TreeNode(3);
        TreeNode t9 = new TreeNode(9);
        TreeNode t20 = new TreeNode(20);
        TreeNode t15 = new TreeNode(15);
        TreeNode t7 = new TreeNode(7);

        t3.left = t9;
        t3.right = t20;
        t20.left = t15;
        t20.right = t7;

        System.out.println(new MinDepth().minDepth(t3));
    }

    Integer minDepth = Integer.MAX_VALUE;

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root, 1);
        return minDepth;
    }

    private void dfs(TreeNode root, int i) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            minDepth = Math.min(i, minDepth);
        }
        dfs(root.left, i + 1);
        dfs(root.right, i + 1);
    }


    /**
     * 在层序遍历的过程中找到叶子节点的深度，比较并记录最小的深度，ac，代码效率不高
     *
     * @param root
     * @return
     */
//    public int minDepth(TreeNode root) {
//        if (root == null) {
//            return 0;
//        }
//        Deque<TreeNode> list = new LinkedList<>();
//        list.push(root);
//        Integer minDepth = Integer.MAX_VALUE;
//        int curDepth = 0;
//        while (!list.isEmpty()) {
//            int size = list.size();
//            for (int i = 0; i < size; i++) {
//                TreeNode poll = list.poll();
//                if (poll.right != null) {
//                    list.add(poll.right);
//                }
//                if (poll.left != null) {
//                    list.add(poll.left);
//                }
//                if (poll.right == null && poll.left == null) {
//                    minDepth = Math.min(minDepth, curDepth);
//                    return minDepth+1;
//                }
//            }
//            curDepth++;
//        }
//        return minDepth+1;
//    }


}
